from collections import deque


class BinTreeNode(object):
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None

    def __repr__(self):
        return self.data


# 前序遍历 先遍历根节点，再遍历左子树，然后右子树
def pre_order(node):
    if node:
        print(node.data, end=',')
        pre_order(node.left_child)
        pre_order(node.right_child)


# 中序遍历 先遍历左子树，再遍历根节点，然后右子树
def mid_order(node):
    if node:
        mid_order(node.left_child)
        print(node.data, end=',')
        mid_order(node.right_child)


# 后序遍历 先遍历左子树，再遍历右子树，最后遍历根节点
def post_order(node):
    if node:
        post_order(node.left_child)
        post_order(node.right_child)
        print(node.data, end=',')


# 层次遍历
def level_order(node):
    queue = deque()
    queue.append(node)
    # 只要队不空
    while len(queue) > 0:
        n = queue.popleft()
        print(n.data, end=',')
        # 如果左节点存在，入队
        if n.left_child:
            queue.append(n.left_child)
        # 如果右节点存在，入队
        if n.right_child:
            queue.append(n.right_child)


a = BinTreeNode(17)
b = BinTreeNode(5)
c = BinTreeNode(25)
d = BinTreeNode(2)
e = BinTreeNode(11)
f = BinTreeNode(35)
g = BinTreeNode(9)
h = BinTreeNode(16)
i = BinTreeNode(29)
j = BinTreeNode(38)
k = BinTreeNode(-1)
a.left_child = b
a.right_child = c
b.left_child = d
b.right_child = e
c.right_child = f
e.left_child = g
e.right_child = h
f.left_child = i
f.right_child = j
g.left_child = k

mid_order(a)
# pre_order(a)
# post_order(a)


# a = BinTreeNode('A')
# b = BinTreeNode('B')
# c = BinTreeNode('C')
# d = BinTreeNode('D')
# e = BinTreeNode('E')
# f = BinTreeNode('F')
# g = BinTreeNode('G')
# a.left_child = b
# b.left_child = d
# b.right_child = e
# a.right_child = c
# c.left_child = f
# c.right_child = g
# # print(c.left_child)
# # pre_order(a)
# # mid_order(a)
# # post_order(a)
# level_order(a)
